﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>

////找单身狗
//int cmp(const void* e1, const void* e2)
//{
//	return *(int*)e1 - *(int*)e2;
//}
////异或版本_有bug
////bug_当单身狗为一个，且为出现过的数时，会运算错误
////两条单身狗无任何错误
//int findDog(const int* pa, int len, int* ps)
//{
//	int i = 0;
//	int ret = 0;
//	int sum = 0;
//	for (i = 0; i < len; i++)
//	{
//		sum += *(pa + i);
//		ret ^= *(pa + i);
//	}
//	if (!(*pa) && !(sum % 2))
//		return 0;
//	for (i = 0; i < len; i++)
//	{
//		int j = 0;
//		int dog = ret ^ *(pa + i);
//		int tmp = 0;
//		for (j = i + 1; j < len; j++)
//		{
//			if ((dog ^ *(pa + j)) == 0)
//			{
//				*(ps + 0) = *(pa + i);
//				*(ps + 1) = *(pa + j);
//				return 1;
//			}
//		}
//	}
//	return 0;
//}
//int main()
//{
//	int arr[] = { 1,1,2,2,3,3,5,9 };
//	int singleDog[2] = { 0 };
//	int len = sizeof(arr) / sizeof(arr[0]);
//	qsort(arr, len, sizeof(arr[0]), cmp);
//	int ret = findDog(arr, len, singleDog);
//	if (1 == ret)
//		printf("找到了,单身狗->%d 单身狗->%d\n", singleDog[0], singleDog[1]);
//	else
//		printf("没有找到两条单身狗!\n");
//	return 0;
//}

////右移寻异版
//void findTwoNum(int arr[], int n, int* pnum1, int* pnum2)
//{
//	int sum = 0;//异或和
//	int i = 0;
//	for (i = 0; i < n; i++)
//	{
//		sum ^= arr[i];
//	}
//	int pos = 0;//移动数
//	for (i = 0; i < 32; i++)
//	{
//		if ((sum>>i) & 1)
//		{
//			pos = i;
//			break;
//		}
//	}
//	*pnum1 = *pnum2 = 0;//先归零，确保异或正确
//	for (i = 0; i < n; i++)
//	{
//		if ((arr[i] >> pos) & 1)
//			*pnum1 ^= arr[i];//如果移动pos并且异或结果为1
//		else
//			*pnum2 ^= arr[i];//否则
//	}
//}
//int main()
//{
//	int arr[] = { 1,1,2,2,3,3,4,4,7,5 };
//	int num1 = 0;
//	int num2 = 0;
//	int len = sizeof(arr) / sizeof(arr[0]);
//	findTwoNum(arr, len, &num1, &num2);
//	printf("%d %d\n", num1, num2);
//	return 0;
//}

////找单身狗，出自力扣260题
//#include<assert.h>
//int* singleNumber(int* nums, int numsSize, int* returnSize) {
//	*returnSize = 2;
//	int* pa = (int*)malloc(sizeof(int) * 2);
//	assert(pa);
//	int sum = 0;//异或和
//	int i = 0;
//	for (i = 0; i < numsSize; i++)
//	{
//		sum ^= nums[i];
//	}
//	int pos = 0;//移动数
//	for (i = 0; i < 32; i++)
//	{
//		if ((sum >> i) & 1)
//		{
//			pos = i;
//			break;
//		}
//	}
//	int num1 = 0;
//	int num2 = 0;
//	for (i = 0; i < numsSize; i++)
//	{
//		if ((nums[i] >> pos) & 1)
//			num1 ^= nums[i];//如果移动pos并且异或结果为1
//		else
//			num2 ^= nums[i];//否则
//	}
//	pa[0] = num1;
//	pa[1] = num2;
//	return pa;
//}
//int main()
//{
//	int arr[] = { 1, 2, 1, 3, 2, 5 };
//	int len = 0;
//	int* p = singleNumber(arr, 6, &len);
//	int i = 0;
//	for (i = 0; i < len; i++)
//	{
//		printf("%d ", p[i]);
//	}
//	return 0;
//}